English+GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Combsort</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Combsort</span></h1>

</header>

</div>

<p><b>Combsort</b> (von <span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic">comb</span>, Kamm) ist ein im April 1991 im <i>BYTE magazine</i> von S. Lacey und R. Box vorgestellter, vom <a href="Bubblesort" title="Bubblesort">Bubblesort</a> abgeleiteter, <a href="Stabilit%C3%A4t_(Sortierverfahren)" title="Stabilität (Sortierverfahren)">nicht-stabiler</a> <a href="In-place" class="mw-redirect" title="In-place">In-place</a>-<a href="Sortierverfahren" title="Sortierverfahren">Sortieralgorithmus</a>, der eine Folge linear angeordneter Elemente (z. B. Zahlen, Alphabete) einem Vergleichskriterium (z. B. der Größe) nach anordnet.

</p>

<div class="mw-heading mw-heading2"><h2 id="Prinzip">Prinzip</h2></div>

<p>Anders als Bubblesort, der nur jeweils benachbarte Elemente vergleicht und ggf.

vertauscht, beginnt Combsort zunächst mit weit auseinanderliegenden Elementen (engl. <i>Gap</i> = Lücke).

Dadurch finden grob falsch sortierte Elemente schneller ihre Zielposition. Nach jedem Durchlauf

wird die Lücke mit Division durch 1,3 verkleinert und der Vorgang wiederholt.

Durch diesen <a href="Empirie" title="Empirie">empirisch</a> gefundenen krummen Divisor wird erreicht, dass sich angrenzende Bereiche in aufeinanderfolgenden Durchläufen stets überlappen und keine <a href="Cluster_(Datenanalyse)" title="Cluster (Datenanalyse)">Cluster</a> bilden, die erst in späteren Durchläufen aufgelöst würden.

</p><p>Der Algorithmus endet, wenn mindestens ein Durchlauf mit <i>Gap</i> =1 erfolgt und keine Vertauschung mehr stattgefunden hat.

</p><p>Bei diesem Endwert <i>Gap</i> =1 ist er am Ende praktisch identisch mit dem Bubblesort, und die Richtigkeit der Sortierung ist bewiesen.

</p><p>Zum Namen: Das zu sortierende Feld wird quasi wie mit einem Kamm (<span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic">comb</span>) mit immer dichter werdenden Zähnen durchgekämmt.

</p><p>Combsort ähnelt dem auf <a href="Insertionsort" title="Insertionsort">Insertionsort</a> basierenden <a href="Shellsort" title="Shellsort">Shellsort</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Komplexität"><span id="Komplexit.C3.A4t"></span>Komplexität</h2></div>

<p>Die Komplexität liegt je nach Ausgangssituation zwischen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"></span> (<a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Worst-Case</a>) und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n\log(n))}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\log(n))}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/75ac2d2b1318fe271226ab13f0eb6c0129df930f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.617ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\log(n))}" loading="lazy"></span> (Best-Case).

</p><p>Im Best-Case ist die Liste der zu sortierenden Elemente geordnet, sobald die Schrittlänge 1 beträgt.

</p><p>Im Worst-Case müssen alle benachbarten Elemente nochmals getauscht werden (mehrere Durchgänge mit Schrittlänge 1). In diesem Fall ist Combsort nicht schneller als <a href="Bubblesort" title="Bubblesort">Bubblesort</a>.

</p><p>Der Avg. Case ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"></span>, analog zu Bubblesort.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formaler_Algorithmus">Formaler Algorithmus</h2></div>

<p>Im <a href="Pseudocode" title="Pseudocode">Pseudocode</a> sieht der CombSort-<a href="Algorithmus" title="Algorithmus">Algorithmus</a> so aus:

</p>

<pre><b>prozedur</b> combSort ( A: Liste sortierbarer Elemente )

schritt:= Länge ( A )

<b>wiederhole</b>

vertauscht:= falsch

<b>für jedes</b> i <b>von</b> 0 <b>bis</b> (Länge ( A ) - schritt) <b>wiederhole</b>

<b>falls</b> ( A[ i ] > A[i + schritt]) <b>dann</b>

vertausche ( A [ i ], A [ i + schritt ] )

vertauscht:= wahr

<b>falls ende</b>

<b>falls</b> (schritt > 1) <b>dann</b>

schritt:= Ganzzahl ( schritt/1.3 )

vertauscht := wahr

<b>falls ende</b>

<b>solange</b> (vertauscht == wahr <b>oder</b> schritt > 1)

<b>prozedur ende</b>

</pre>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Stephen Lacey, Richard Box: <cite style="font-style:italic">A Fast Easy Sort</cite>. In: <cite style="font-style:italic">Byte Magazine</cite>. April 1991 (<a rel="nofollow" class="external text" href="http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm">cs.clackamas.cc.or.us</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Combsort&rft.atitle=A+Fast+Easy+Sort&rft.au=Stephen+Lacey%2C+Richard+Box&rft.btitle=Byte+Magazine&rft.date=1991-04&rft.genre=book" style="display:none"> </span></li>

<li>Wlodzimierz Dobosiewicz: <cite style="font-style:italic">An efficient variation of bubble sort</cite>. In: <cite style="font-style:italic">Information Processing Letters</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>11</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, 1980, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>5–6</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1016/0020-0190%2880%2990022-8">10.1016/0020-0190(80)90022-8</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Combsort&rft.atitle=An+efficient+variation+of+bubble+sort&rft.au=Wlodzimierz+Dobosiewicz&rft.date=1980&rft.doi=10.1016%2F0020-0190%2880%2990022-8&rft.genre=journal&rft.issue=1&rft.jtitle=Information+Processing+Letters&rft.pages=5-6&rft.volume=11" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"><span class="mw-default-size" typeof="mw:File"><span title="Commons"></span></span></div><b><span class=""><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Sort_algorithms?uselang=de"><span lang="en">Commons</span>: Sortieralgorithmen</a></span></b> – Sammlung von Bildern, Videos und Audiodateien</div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"><span class="mw-default-size" typeof="mw:File"><span title="Wikibooks"></span></span></div><b><a href="https://de.wikibooks.org/wiki/Algorithmensammlung:_Sortierverfahren:_Combsort" class="extiw external" title="b:Algorithmensammlung: Sortierverfahren: Combsort">Wikibooks: Combsort</a></b> – Implementierungen in der Algorithmensammlung</div>

/* start https://de.wikipedia.org/ */

.mw-parser-output .webarchiv-memento a{color:inherit}

/* end https://de.wikipedia.org/ */

</style><a rel="nofollow" class="external text" href="https://web.archive.org/web/20050419014554/http://objectz.com/columnists/leif/07242000.htm">Combsort</a> (<span class="webarchiv-memento"><a href="Webarchivierung#Begrifflichkeiten" title="Webarchivierung">Memento</a></span> vom 19. April 2005 im <i><a href="Internet_Archive" title="Internet Archive">Internet Archive</a></i>) bei <i>Computer Science for the COBOL Community</i></li>

<li><a rel="nofollow" class="external text" href="https://www.sortieralgorithmen.de/combsort">Combsort</a> bei sortieralgorithmen.de</li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-10-26" href="https://de.wikipedia.org/wiki/?title=Combsort&oldid=260940677">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>